/**
 * Project Name:JavaBaseReview
 * Package Name:com.xuwei.base.search
 * author:David
 * Date:2016年5月21日上午11:03:01
 * Copyright (c) 2016, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.search;

import com.xuwei.base.tree.BinTreeNode;

/**
 * 平衡二叉树（AVL树）:使用AVL算法
 * @author David
 * @since 2016年5月21日 上午11:03:01
 * @version 
 * @since JDK 1.6
 */
public class AVLTree extends BinSearchTree{
	
	
	/**
	 * 
	 */
	public AVLTree() {
		super(null);
	}
	/**
	 * @param root
	 */
	public AVLTree(BinTreeNode root) {
		super(root);
	}

	@Override
	public void insert(Object ele){
		super.insert(ele);
		root = reBalance(startBN);
	}
	
	/**
	 * 从v开始重新平衡AVL树
	 * @param v
	 * @return
	 */
	private BinTreeNode reBalance(BinTreeNode v){
		if(v==null){
			return root;
		}
		BinTreeNode c = v;
		while(v!=null){   //从v开始，向上逐一检查z的祖先
			if(!isBalance(v)){ //若v失衡，则旋转使之重新平衡 
				v = rotate(v);
			}
			c = v;
			v = v.getParent(); //继续检查其父亲
		}//while
		return c;
	}
	/**
	 * 判断一个结点是否平衡
	 * @param v
	 * @return
	 */
	private boolean isBalance(BinTreeNode v){
		if(v==null){
			return true;
		}
		int lH = (v.hasLChild())?v.getLChild().getHeight():-1;
		int rH = (v.hasRChild())?v.getRChild().getHeight():-1;
		return (Math.abs(lH - rH)<=1);
	}
	
	/**
	 * 在AVL树中删除ele
	 */
	public Object remove(Object ele){
		Object obj = super.remove(ele);
		root = reBalance(startBN);
		return obj;
	}
	
	/**
	 * 旋转
	 * @param z
	 * @return
	 */
	private BinTreeNode rotate(BinTreeNode z){
		BinTreeNode y = higherSubT(z); //取y为z更高的孩子
		BinTreeNode x = higherSubT(y); //取x为y更高的孩子
		boolean isLeft = z.isLChild(); //记录：z是否左孩子
		BinTreeNode p = z.getParent(); //p为z的父亲
		BinTreeNode a, b, c;           //自左向右，三个结点
		BinTreeNode t0, t1, t2, t3;    //自左向右，四棵子树
		//以下分四种情况重命名
		if(y.isLChild()){
			c = z;
			t3 = z.getRChild();
			if(x.isLChild()){ //若x是左子树（左右失衡）
				b = y;
				t2 = y.getRChild();
				a = x;
				t1 = x.getRChild();
				t0 = x.getLChild();
			}else{           //若x是右子树（左右失衡）
				a = y;
				t0 = y.getLChild();
				b = x;
				t1 = x.getLChild();
				t2 = x.getRChild();
			}
		}else{    
			a = z;
			t0 = z.getLChild();
			if(x.isRChild()){
				b = y;
				t1 = y.getLChild();
				c = x;
				t2 = x.getLChild();
				t3 = x.getRChild();
			}else{
				c = y;
				t3 = y.getRChild();
				b = x;
				t1 = x.getLChild();
				t2 = x.getRChild();
			}
		}
		//摘下三个结点
		z.sever();
		y.sever();
		x.sever();
		//摘下四棵子树
		if(t0!=null){
			t0.sever();
		}
		if(t1!=null){
			t1.sever();
		}
		if(t2!=null){
			t2.sever();
		}
		if(t3!=null){
			t3.sever();
		}
		//重新链接
		a.setLChild(t0);
		a.setRChild(t1);
		
		c.setLChild(t2);
		c.setRChild(t3);
		
		b.setLChild(a);
		b.setRChild(c);

		//子树重新接入原树
		if(p!=null){
			if(isLeft){
				p.setLChild(b);
			}else{
				p.setRChild(b);
			}
		}
		return b;//返回新的子树根
		
	}
	
	/**
	 * 返回结点v较高的子树
	 * @param v
	 */
	private BinTreeNode higherSubT(BinTreeNode v){
		if(v==null){
			return null;
		}
		int lH = (v.hasLChild())?v.getLChild().getHeight():-1;
		int rH = (v.hasRChild())?v.getRChild().getHeight():-1;
		if(lH>rH){
			return v.getLChild();
		}
		if(lH<rH){
			return v.getRChild();
		}
		if(v.isLChild()){
			return v.getLChild();
		}else{
			return v.getRChild();
		}
	}
	
}
